package leetcode.code0913;

/**
 * 这是错的
 *
 * @author CaoYu
 * @date 2022年1月4日
 * @description
 */
public class Solution3 extends Solution913 {

	int WIN_MOUSE = 1;
	int WIN_CAT = 2;
	int WIN_NONE = 0;

	@Override
	public int catMouseGame(int[][] graph) {
		int n = graph.length;
		Integer[][][] dp = new Integer[n][n][n << 1];
		return this.mouseMove(0, 1, 2, graph, dp);
	}

	private int mouseMove(int step, int mouseAt, int catAt, int[][] graph, Integer[][][] dp) {
		if (step >= (graph.length * graph.length << 1)) {// 就差这一手没想到啊没想到。
			return this.WIN_NONE;
		}
		if (mouseAt == 0) {
			return this.WIN_MOUSE;
		}
		if (mouseAt == catAt) {
			return this.WIN_CAT;
		}
		if (dp[mouseAt][catAt][step] != null) {
			return dp[mouseAt][catAt][step];
		}
		int winner = this.WIN_CAT;
		int[] path = graph[mouseAt];
		for (int next : path) {
			int cur_result = this.catMove(step + 1, next, catAt, graph, dp);
			if (cur_result == this.WIN_MOUSE) {
				dp[mouseAt][catAt][step] = this.WIN_MOUSE;
				return this.WIN_MOUSE;
			} else if (cur_result == this.WIN_NONE) {
				winner = this.WIN_NONE;
			}
		}
		dp[mouseAt][catAt][step] = winner;
		return winner;
	}

	private int catMove(int step, int mouseAt, int catAt, int[][] graph, Integer[][][] dp) {
		if (step >= (graph.length * graph.length << 1)) {// 就差这一手没想到啊没想到。
			return this.WIN_NONE;
		}
		if (mouseAt == 0) {
			return this.WIN_MOUSE;
		}
		if (mouseAt == catAt) {
			return this.WIN_CAT;
		}
		if (dp[mouseAt][catAt][step] != null) {
			return dp[mouseAt][catAt][step];
		}
		int winner = this.WIN_MOUSE;
		int[] path = graph[catAt];
		for (int next : path) {
			if (next == 0) {// 猫不让走0
				continue;
			}
			int cur_result = this.mouseMove(step + 1, mouseAt, next, graph, dp);
			if (cur_result == this.WIN_CAT) {
				dp[mouseAt][catAt][step] = this.WIN_CAT;
				return this.WIN_CAT;
			} else if (cur_result == this.WIN_NONE) {
				winner = this.WIN_NONE;
			}
		}
		dp[mouseAt][catAt][step] = winner;
		return winner;
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
